package oj;

import org.apache.commons.collections.CollectionUtils;

import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
import java.util.Scanner;

/**
 * @author chaolong.jin
 * @description
 * @date 2019/07/01 15:13
 */
public class MergeSort {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            int n = scanner.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = new Random().nextInt(n);
                System.out.print(a[i] + " ");
            }
            System.out.println();
            split(a, 0, n - 1);
            System.out.println(Arrays.toString(a));
//            for (int i = 0; i < n; i++) {
//                System.out.print(a[i] + " ");
//            }
        }

    }

    private static void split(int[] a, int low, int height) {
        int length = height - low;
//        if (length < 7) {
//            for (int p = low; p <= height; p++) {
//                for (int q = p + 1; q <= height; q++) {
//                    if (a[p] > a[q]) {
//                        swap(a, p, q);
//                    }
//                }
//            }
//            return;
//        }
        if (low < height) {
            int mid = (low + height) / 2;
            split(a, low, mid);
            split(a, mid + 1, height);
            merge(a, low, mid, height);
        }
    }

    private static void merge(int[] a, int low, int mid, int height) {
        int i = low;
        int j = mid + 1;
        int[] temp = new int[a.length];
        int index = low;
        while (i <= mid && j <= height) {
            if (a[i] <= a[j]) {
                temp[index++] = a[i++];
            } else {
                temp[index++] = a[j++];
            }
        }
        while (i <= mid) {
            temp[index++] = a[i++];
        }
        while (j <= height) {
            temp[index++] = a[j++];
        }
        int t = low;
        while (t <= height) {
            a[t] = temp[t++];
        }
    }

    private static void swap(int[] arrays, int a, int b) {
        int temp = arrays[a];
        arrays[a] = arrays[b];
        arrays[b] = temp;
    }
}
